Okay, we have these tree search algorithms and essentially what we're doing is we're

stepping through the tree, expanding nodes, collecting up a fringe, and now the important

thing comes, we have a strategy for selecting stuff, the next node from the fringe, and

that's really what we're studying here.

Okay, here we're doing breadth-first search where we treat the fringe as a queue, first

in, first out, and that means we have essentially fringes that can grow to the level, to the

size of a whole level, and the levels are exponentially big, so we get exponential time

and space behavior.

Here you can see this very nicely, the fringe is the whole level here.

Okay, so what's our tally here?

We have completeness, we will find solutions if they exist.

Time complexity is exponential, it's terrible, space complexity is exponential, it's terrible,

optimality is not even given.

That is because we are exploring the tree straight level by straight level by straight

level, and sometimes the cheap, the optimal solutions are a little bit down because costs

may vary.

If costs are constant, essentially one per step, then we're optimal, otherwise not.

Yes, wait.

Yes.

That's really how you count, I start counting depth at zero, and that gives you the plus

one.

That means you have two to the D in a binary tree down there, and all the rest is essentially

again two to the D, that's the plus one.

Thanks.

Good, so I've looked a little bit around, the numbers weren't very good yesterday, but

we can by now generate 500 megabytes per second, which is about what you can write onto a modern

SSD.

Which means you can, if you have one of these shiny new two terabyte SSDs, which most of

us don't, but you can buy them, then in an hour that's full.

Then you have to do something which is even slower.

You run out of space much earlier than you run out of time, so there's no way you can,

on a laptop or so, survive longer than searching one or two hours in a breath-first search.

Space is a problem, time is also a problem, but not that much.

If you look at it, at that time, if you have a binary tree or something like this, you're

somewhere at, what is it, terabyte 10 to the 12 or so, you're 12 deep or so.

Now binary tree, you're 12 times 3 deep.

Even if you just have a lot of space, you're not searching very far.

You can't do breath-first search on chess, because a chess game is much longer than just

30 or so moves.

The next thing we talked about, we wanted to fix, was the optimality problem.

That's relatively easy to fix.

Instead of searching by level, you search by ISO cost line, which means the same costs

at that level for a level.

That gives you optimality.

There's not really much to be said.

Their completeness might go down the drain if we're not very careful with costs.

If we don't find the costs from below, it could be that we get into paths where the

whole cost is small, but that are infinitely long.

If that happens, we're losing completeness.

Otherwise, it behaves like breath-first search.